package 剑指Offer;

public class Offer43_1到n整数中1出现的次数 {
    public int countDigitOne(int n) {

        // 设计按照 “个位、十位、...” 的顺序计算，最开始cur为个位
        int digit = 1, res = 0;
        int high = n / 10, cur = n % 10, low = 0;
        while (high != 0 || cur != 0) {//当 high 和 cur 同时为 0 时，说明已经越过最高位，因此跳出
            //下面三个if else就是推出来的公式
            if (cur == 0) {
                res += high * digit;
            } else if (cur == 1) {
                res += high * digit + low + 1;
            } else {
                res += (high + 1) * digit;
            }
            low += cur * digit;//将 cur 加入 low ，组成下轮 low
            cur = high % 10;//下轮 cur 是本轮 high 的最低位
            high /= 10;//将本轮 high 最低位删除，得到下轮 high
            digit *= 10;//位因子每轮 × 10
        }
        return res;
    }
}
